package ljl.alg.wangzheng_camp.round1.bisection;

import java.util.LinkedHashMap;
import java.util.LinkedList;
import java.util.Map;

public class _03_06_animal_shelf {
    
    /*
     * 意思是，你要么取猫和狗中最老的，或你指定种类，然后取这个种类里最老的
     * */
    class AnimalShelf {
        Map<Integer, int[]> all = new LinkedHashMap<>();
        LinkedList<int[]> cats = new LinkedList<>();
        LinkedList<int[]> dogs = new LinkedList<>();
        int[] NIL = {-1, -1};
        
        /**
         * int[2]: int[0] 编号 int[1] 种类 0 猫，1 狗
         */
        public void enqueue(int[] animal) {
            all.put(animal[0], animal);
            if (animal[1] == 0)
                cats.offer(animal);
            else dogs.offer(animal);
        }
        
        public int[] dequeueAny() {
            if (all.size() == 0) return NIL;
            final Map.Entry<Integer, int[]> first = all.entrySet().iterator().next();
            all.remove(first.getKey());
            if (first.getValue()[1] == 0) return cats.poll();
            else return dogs.poll();
        }
        
        public int[] dequeueDog() {
            if (dogs.size() == 0) return NIL;
            final int[] dog = dogs.poll();
            all.remove(dog[0]);
            return dog;
        }
        
        public int[] dequeueCat() {
            if (cats.size() == 0) return NIL;
            final int[] cat = cats.poll();
            all.remove(cat[0]);
            return cat;
        }
    }
    
    /*
    * 也不快反正
    * 比我那个 map 的好点，可能
    * */
    class AnimalShelf2 {
        LinkedList<int[]> cats = new LinkedList<>();
        LinkedList<int[]> dogs = new LinkedList<>();
        int[] NIL = {-1, -1};
        
        public void enqueue(int[] animal) {
            if (animal[1] == 0)
                cats.offer(animal);
            else dogs.offer(animal);
        }
        
        public int[] dequeueAny() {
            if (cats.size() == 0 && dogs.size() == 0) return NIL;
            if (cats.size() == 0) return dogs.poll();
            if (dogs.size() == 0) return cats.poll();
            int[] dog = dogs.peekFirst(), cat = cats.peekFirst();
            if (dog[0] < cat[0]) return dogs.poll();
            return cats.poll();
        }
        
        public int[] dequeueDog() {
            if (dogs.size() == 0) return NIL;
            return dogs.poll();
        }
        
        public int[] dequeueCat() {
            if (cats.size() == 0) return NIL;
            return cats.poll();
        }
    }
    
}
